package leetcode_600;

import java.util.HashMap;
import java.util.Map;

/**
 *@author 周杨
 *ContiguousArray_525_ 找出一个二进制数组里的最长子数组 这个数组必须含有相同数量的0 和1
 *describe:用数组和方法 可以在O(n)时间复杂度内解决问题 AC 45%
 *2018年9月10日 下午1:43:35
 */
public class ContiguousArray_525_ {
	
	public static void main(String[] args) {
		ContiguousArray_525_ test=new ContiguousArray_525_();
		test.findMaxLength(new int[] {0,0,1,0,1});
	}
	
	 /**
	 * describe:非常巧妙的办法 用数组和计算 o(n)时间复杂度 C 45%
	 * 2018年9月10日 下午1:42:23
	 */
	public int findMaxLength(int[] nums) {
	        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
	        map.put(0,-1);
	        int sum= 0;
	        int max = 0;
	        for(int i=0;i<nums.length;i++){
	            sum+=nums[i]==0?-1:1;
	            if(map.containsKey(sum)){
	                max = Math.max(max,i-map.get(sum));
	            }else{
	                map.put(sum,i);
	            }
	        }
	        return max;
	    }
	
	 /**
	 * describe:动态规划解决 O(n^2)时间复杂度  可惜超时 
	 * 2018年9月10日 下午12:46:17
	 */
	public int findMaxLength1(int[] nums) {
		 if(nums.length<2)
			 return 0;
		 int dp[]=new int[nums.length];//记录J到当前 0出现的次数
		 int res=0;
		 for(int i=0;i<nums.length;++i) {
			 boolean flag=nums[i]==0?true:false;
			 dp[i]=flag?1:0;
			 for(int j=0;j<i;++j) {
				 if(flag)
					 dp[j]++;
				 int diff=i-j+1;
				 if(diff%2==0) {//该区间是偶数
					 if(dp[j]*2==diff) {//刚好是一半
						 res=Math.max(res,diff);
					 }
				 }
			 }
		 }
		 return res;
	 }
	
	/**
	 * describe:改为遇到0 -1 遇到1 +1 用动归 仍然超时
	 * 2018年9月10日 下午12:53:50
	 */
	public int findMaxLength2(int[] nums) {
		 if(nums.length<2)
			 return 0;
		 int dp[]=new int[nums.length];//
		 int res=0;
		 for(int i=0;i<nums.length;++i) {
			 dp[i]=nums[i]==1?1:-1;
			 for(int j=0;j<i;++j) {
				 dp[j]+=dp[i];
				 if(dp[j]==0)
					 res=Math.max(res, i-j+1);
			 }
		 }
		 return res;
	 }
}
